package com.huangyi;

public class Main {
    public static void main(String[] args) {
        //寻找峰值
        class Solution {
            public int peakIndexInMountainArray(int[] arr) {
                int left = 1, right = arr.length - 2; // 峰不在两端，且要用到 mid-1
                while (left < right) {
                    int mid = left + (right - left + 1) / 2; // 上中位数
                    if (arr[mid] > arr[mid - 1]) {
                        left = mid;          // 上坡：峰在 [mid, right]
                    } else {
                        right = mid - 1;     // 下坡：峰在 [left, mid-1]
                    }
                }
                return left; // 即峰顶索引
            }
        }


        //山脉数组的峰顶索引
        class Solution2 {
            public int peakIndexInMountainArray(int[] arr) {
                int n = arr.length;
                int left = 1, right = n - 2; // 峰不在两端，且需访问 arr[mid-1]

                while (left < right) {
                    int mid = left + (right - left + 1) / 2; // 上中位数
                    if (arr[mid] > arr[mid - 1]) {
                        // 上坡：峰在 [mid, right]，保留 mid
                        left = mid;
                    } else {
                        // 下坡：峰在 [left, mid-1]，丢弃 mid
                        right = mid - 1;
                    }
                }
                return left; // 或 right
            }
        }

    }
}